//
// Created by user on 2022/3/15.
//

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
    };

ListNode* partition(ListNode* head, int x) {
    if (!head || !head->next) return head;

    ListNode *smallHead = new ListNode(-1);
    ListNode *small = smallHead;
    ListNode *largeHead = new ListNode(-1);
    ListNode *large = largeHead;

    while (head) {
        if (head->val < x) {
            small->next = head;
            small = small->next;
        } else {
            large->next = head;
            large = large->next;
        }
        head = head->next;
    }

    small->next = largeHead->next;
    large->next = nullptr;

    return smallHead->next;
}